package com.likou;

import java.util.*;

/**
 * Author: 陈桂明
 * Date: 2025/4/13 13:52
 * Description: q56
 */
public class q56 {
    public static void main(String[] args) {
        int[][] a = new int[][]{new int[]{1, 3}, new int[]{2, 6}, new int[]{8, 10}, new int[]{15, 18}};
        int[][] merge = new q56().merge(a);
        for (int[] i : merge) {
            System.out.println(Arrays.toString(i));
        }
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 1 || intervals.length == 0) {
            return intervals;
        }

        List<int[]> ans = new ArrayList<>();
        int index = 0;

        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        for (int i = 0; i < intervals.length; i++) {
            if (ans.size() != 0 && ans.get(index - 1)[1] >= intervals[i][0]) {
                ans.get(index - 1)[1] = Math.max(ans.get(index - 1)[1], intervals[i][1]);
            } else {
                ans.add(intervals[i]);
                index++;
            }
        }

        return ans.toArray(new int[ans.size()][]);
    }


    // public int[][] merge(int[][] intervals) {
    //     List<List<Integer>> lists = new ArrayList<>();
    //     // int[][] ans = new int[intervals.length][2];
    //     List<int[]> ans = new ArrayList<>();
    //     int index = 0;
    //     for (int i = 0; i < intervals.length; i++) {
    //         int[] ints1 = intervals[i];
    //         int t1 = ints1[0];
    //         int t2 = ints1[1];
    //         for (int j = 0; j < intervals.length; j++) {
    //             if (i == j) {
    //                 continue;
    //             }
    //             int[] ints2 = intervals[j];
    //             if ((ints1[1] >= ints2[0] && ints1[1] <= ints2[1]) || (ints1[0] >= ints2[0] && ints1[0] <= ints2[1])) {
    //                 int left = Math.min(ints1[0], ints2[0]);
    //                 int right = Math.max(ints1[1], ints2[1]);
    //                 ints1[0] = left;
    //                 ints1[1] = right;
    //             }
    //         }
    //         if (!lists.contains(Arrays.asList(ints1[0], ints1[1]))) {
    //             // ans[index] = Arrays.copyOf(ints1, 2);
    //             ans.add(Arrays.copyOf(ints1, 2));
    //             index++;
    //         }
    //         lists.add(Arrays.asList(ints1[0], ints1[1]));
    //         ints1[0] = t1;
    //         ints1[1] = t2;
    //     }
    //
    //     for (int i = 0; i < ans.size(); i++) {
    //         int[] a = ans.get(i);
    //         for (int j = 0; j < ans.size(); j++) {
    //             if (i == j) {
    //                 continue;
    //             }
    //
    //             int[] b = ans.get(j);
    //             if ((a[0] >= b[0] && a[0] <= b[1]) || (a[1] >= b[0] && a[1] <= b[1])) {
    //                 ans.remove(b);
    //             }
    //         }
    //     }
    //
    //     return ans.toArray(new int[ans.size()][]);
    // }
}
